package com.leetcode.algorithm.y22.m06;

import java.util.ArrayList;
import java.util.List;

/**
 * 77. 组合
 * 
 * https://leetcode.cn/problems/combinations/
 * 
 * @author jie.deng
 *
 */
class Question0077Solution01 {
	
	public List<List<Integer>> combine(int n, int k) {
		List<List<Integer>> retList = new ArrayList<>();
		List<Integer> curList = new ArrayList<>();
		combine(n, k, 1, curList, retList);
		return retList;
	}

	/**
	 * 
	 * @param n
	 * @param k
	 * @param curN 当前待考察的元素
	 * @param curList 当前已选的元素集合
	 * @param retList
	 */
	private void combine(int n, int k, int curN, List<Integer> curList, List<List<Integer>> retList) {
		// 递归终止条件
		if (curList.size() == k) {
			retList.add(new ArrayList<>(curList));
			return;
		}
		if (curN > n) {
			return;
		}
		// 剪枝
		if (curList.size() + (n - curN + 1) < k) {
			return;
		}

		// 包含当前元素
		curList.add(curN); // 当前层逻辑
		combine(n, k, curN + 1, curList, retList); // 递归调用

		curList.remove(curList.size() - 1); // 恢复当前层的状态
		// 不包含当前元素
		combine(n, k, curN + 1, curList, retList);// 递归调用
	}
    
}